/**
 * Initialize your data structure here.
 * @author dingyue.zhf
 * @description 1339. 分裂二叉树的最大乘积 https://leetcode-cn.com/problems/maximum-product-of-splitted-binary-tree/

 */

/**
 * 动态规划，每次选择乘积最大的二叉树
 * 和的乘积，最大，越接近乘积越大，取abs
 * 递归决定是加左边还是加右边
 * 只需要返回和的乘积
 * @param {*} root
 */

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxProduct = function (root) {
  let ans, total, avg;
  const getTotal = (node) => {
    if (!node) {
      return 0;
    }
    const val = getTotal(node.left) + getTotal(node.right) + node.val;
    // NaN < NaN 为false
    if (Math.abs(avg - val) < Math.abs(avg - ans)) {
      ans = val;
    }
    return val;
  };
  total = getTotal(root);
  avg = total / 2;
  ans = total;
  getTotal(root);
  // 10e9 + 7
  // 10 ** 9 + 7
  return (ans * (total - ans)) % (10 ** 9 + 7);
};
